网络流24题

其实只有 2121 道题。两道不是网络流,另一道是假题。

一.最大流问题

简单题

1.P2756 飞行员配对方案问题

经典的二分图最大匹配。

建立源点与汇点,分别向二分图的其中一部分连容量为 11 的边。

可匹配的点之间也连一条边,容量随意。

最后跑最大流即可。

方案可以根据残余网络构造出来。

2.P3254 圆桌问题

3.P2763 试题库问题

中等题

4.P2764 最小路径覆盖问题

首先每个点用一条边覆盖,为了使路径尽可能少,我们要连接一些路径。

将每个点拆成两个点 xi,yix_i,y_i ,对于 uvu \rightarrow v 这条边,连接 xu,yvx_u,y_v 并将容量设为 11,如果这条边有流则表示将 u,vu,v 的路径合并。

然后连接 Sxi,yiTS \rightarrow x_i,y_i\rightarrow T,容量也设为 11 (要求顶点不相交,每个点只能连接一次)

最后图的最大流便是连接的最大数量,答案为 n最大流n-\text{最大流}

方案直接记录后继节点就可以了。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f

const int MAXN = 300 , MAXM = 7000;
struct node {
	int v , flow , nxt;
}Graph[ 2 * MAXM + 5 ];
int tot = 1 , Head[ MAXN + 5 ];
void Add_Edge( int u , int v , int f ) {
	Graph[ ++ tot ] = { v , f , Head[ u ] };
	Head[ u ] = tot;
}

int n , m , s , t;
int lev[ MAXN + 5 ] , cur[ MAXN + 5 ] , nxt[ MAXN + 5 ] , sta[ MAXN + 5 ];
bool Layering( int s , int t ) {
    memset( lev , -1 , sizeof( lev ) );
	memcpy( cur , Head , sizeof( Head ) );
    queue< int > Que;
    Que.push( s ) , lev[ s ] = 0;
    while( !Que.empty( ) ) {
        int u = Que.front( ); Que.pop( );
        for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
            int v = Graph[ i ].v , flw = Graph[ i ].flow;
            if( flw > 0 && lev[ v ] == -1 )
                lev[ v ] = lev[ u ] + 1 , Que.push( v );
        }
    }
    return lev[ t ] != -1;
}

int dfs( int u , int t , int f ) {
	if( u == t ) return f;
	for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
		int v = Graph[ i ].v , flw = Graph[ i ].flow;
		cur[ u ] = i;
		if( flw > 0 && lev[ u ] < lev[ v ] ) {
			int mf = dfs( v , t , min( f , flw ) );
			if( mf ) {
				Graph[ i ].flow -= mf; Graph[ i ^ 1 ].flow += mf;
				if( u != s && v > n ) sta[ v - n ] = 1;
				nxt[ u ] = v;
				return mf;
			}
		}
	}
	return 0;
}

int Dinic( int s , int t ) {
	int Maxf = 0;
	while( Layering( s , t ) ) for( int fl ; ( fl = dfs( s , t , Inf ) ) > 0 ; Maxf += fl );
	for( int i = 1 ; i <= n ; i ++ )
		if( !sta[ i ] ) {
			printf("%d", i );
			int u = i;
			while( nxt[ u ] && nxt[ u ] != t ) {
				printf(" %d", nxt[ u ] - n );
				u = nxt[ u ] - n;
			}
			printf("\n");
		}
	return Maxf;
}

int main( ) {
	scanf("%d %d",&n,&m);
	s = 2 * n + 1 , t = 2 * n + 2;
	for( int i = 1 , u , v ; i <= m ; i ++ ) {
		scanf("%d %d",&u,&v);
		Add_Edge( u , v + n , 1 );
		Add_Edge( v + n , u , 0 );
	}
	for( int i = 1 ; i <= n ; i ++ )
		Add_Edge( s , i , 1 ) , Add_Edge( i , s , 0 );
	for( int i = 1 ; i <= n ; i ++ )
		Add_Edge( i + n , t , 1 ) , Add_Edge( t , i + n , 0 );
    
	
	printf("%d\n", n - Dinic( s , t ) );
	return 0; 
} 

变式:P5769 [JSOI2016]飞机调度 题解

5.P2774 方格取数问题

选出的格子不能相邻,这是此题的关键。

如果两个格子相邻,那么它们坐标和的奇偶性一定不同。

将限制条件看成一条边,那么图是一个二分图。分别从源点和汇点向两部分连边,容量即为格子里的数。

不选格子里的数相当删去于将源点/汇点与该点的边。

求出图的最小割即可。

因为不能改变限制条件,所以二分图内部的容量设为极大值。

注意不要重复建边。

#include <queue>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define Inf 0x3f3f3f3f

const int MAXN = 10000 , MAXM = 6 * MAXN;
struct Edge {
    int v , flw , nxt;
    Edge(){}
    Edge( int V , int Flw , int Nxt ) { v = V , flw = Flw , nxt = Nxt; }
}Graph[ MAXM + 5 ];
int Head[ MAXN + 5 ] , Enum = 1;
void Add_Edge( int u , int v , int flw ) {
    Graph[ ++ Enum ] = Edge( v , flw , Head[ u ] ); Head[ u ] = Enum;
    Graph[ ++ Enum ] = Edge( u , 0   , Head[ v ] ); Head[ v ] = Enum;
}

int cur[ MAXN + 5 ] , lev[ MAXN + 5 ];
bool Layer( int S , int T ) {
    memcpy( cur , Head , sizeof( Head ) );
    memset( lev , -1 , sizeof( lev ) );
    queue< int > Que;
    lev[ S ] = 0 , Que.push( S );
    while( !Que.empty() ) {
        int u = Que.front(); Que.pop();
        for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
            int v = Graph[ i ].v , flw = Graph[ i ].flw;
            if( flw > 0 && lev[ v ] == -1 )
                lev[ v ] = lev[ u ] + 1 , Que.push( v );
        }
    }
    return lev[ T ] != -1;
}
int dfs( int u , int t , int f ) {
    if( u == t ) return f;
    for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
        int v = Graph[ i ].v , flw = Graph[ i ].flw ;
        cur[ u ] = i;
        if( flw > 0 && lev[ u ] < lev[ v ] ) {
            int d = dfs( v , t , min( f , flw ) );
            if( d > 0 ) {
                Graph[ i ].flw -= d , Graph[ i ^ 1 ].flw += d;
                return d;
            }
        }
    }
    return 0;
}
int Dinic( int S , int T ) {
    int Mxf = 0;
    while( Layer( S , T ) ) for( int fl = 0 ; ( fl = dfs( S , T , Inf ) ) > 0 ; Mxf += fl );
    return Mxf;
}

int n , m , a[ 105 ][ 105 ] , Suma , S , T;
int hs( int x , int y ) { return ( x - 1 ) * 100 + y; }
int main( ) {
	scanf("%d %d",&n,&m); S = hs( n + 1 , 1 ) , T = hs( n + 1 , 2 );
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= m ; j ++ )
			scanf("%d",&a[ i ][ j ]) , Suma += a[ i ][ j ];
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= m ; j ++ )
			if( ( i + j ) & 1 ) Add_Edge( S , hs( i , j ) , a[ i ][ j ] );
			else Add_Edge( hs( i , j ) , T , a[ i ][ j ] );
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j <= m ; j ++ )
			if( ( i + j ) & 1 ) {
				if( i != 1 ) Add_Edge( hs( i , j ) , hs( i - 1 , j ) , Inf );
				if( i != n ) Add_Edge( hs( i , j ) , hs( i + 1 , j ) , Inf );
				if( j != 1 ) Add_Edge( hs( i , j ) , hs( i , j - 1 ) , Inf );
				if( j != m ) Add_Edge( hs( i , j ) , hs( i , j + 1 ) , Inf );
			}
	printf("%d\n", Suma - Dinic( S , T ) );
    return 0;
}

6.P2766 最长不下降子序列问题

首先可以 O(n2)\mathcal O(n^2) dp 求得以 ii 结尾的最长不下降子序列。

第一问的答案 s=max{dpi}s=\max\{dp_i\}

然后源点向所有 dpi=1dp_i=1 的点连容量为 11 的边,汇点向所有 dpi=sdp_i=s 的点连容量为 11 的边。

那么 dp 转移可以这样刻画:

对于 j<i,ajai,dpi=dpj+1j<i,a_j \le a_i,dp_i=dp_j+1i,ji,j ,在它们之间连一条容量为 11 的边。

这样不能保证每个点只被选 11 次,所以将每个点拆成两个点即可。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f

const int MAXN = 1000 , MAXM = MAXN * ( MAXN + 2 );
struct Edge {
    int v , flw , nxt;
    Edge(){}
    Edge( int V , int Flw , int Nxt ) { v = V , flw = Flw , nxt = Nxt; }
}Graph[ MAXM + 5 ];
int Head[ MAXN + 5 ] , Enum = 1;
void Add_Edge( int u , int v , int flw ) {
    Graph[ ++ Enum ] = Edge( v , flw , Head[ u ] ); Head[ u ] = Enum;
    Graph[ ++ Enum ] = Edge( u , 0   , Head[ v ] ); Head[ v ] = Enum;
}

int cur[ MAXN + 5 ] , lev[ MAXN + 5 ];
bool Layer( int S , int T ) {
    memcpy( cur , Head , sizeof( Head ) );
    memset( lev , -1 , sizeof( lev ) );
    queue< int > Que;
    lev[ S ] = 0 , Que.push( S );
    while( !Que.empty() ) {
        int u = Que.front(); Que.pop();
        for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
            int v = Graph[ i ].v , flw = Graph[ i ].flw;
            if( flw > 0 && lev[ v ] == -1 )
                lev[ v ] = lev[ u ] + 1 , Que.push( v );
        }
    }
    return lev[ T ] != -1;
}
int dfs( int u , int t , int f ) {
    if( u == t ) return f;
    for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
        int v = Graph[ i ].v , flw = Graph[ i ].flw ;
        cur[ u ] = i;
        if( flw > 0 && lev[ u ] < lev[ v ] ) {
            int d = dfs( v , t , min( f , flw ) );
            if( d > 0 ) {
                Graph[ i ].flw -= d , Graph[ i ^ 1 ].flw += d;
                return d;
            }
        }
    }
    return 0;
}
int Dinic( int S , int T ) {
    int Mxf = 0;
    while( Layer( S , T ) ) for( int fl = 0 ; ( fl = dfs( S , T , Inf ) ) > 0 ; Mxf += fl );
    return Mxf;
}

int n , a[ MAXN + 5 ] , S , T;
int s , dp[ MAXN + 5 ];

int main( ) {
	scanf("%d",&n); S = 2 * n + 1 , T = S + 1;
	for( int i = 1 ; i <= n ; i ++ ) scanf("%d",&a[ i ]);
	
	if( n == 1 ) return printf("%d\n%d\n%d\n",1,1,1) & 0; 
	
	for( int i = 1 ; i <= n ; i ++ ) {
		dp[ i ] = 1;
		for( int j = 1 ; j < i ; j ++ )
			if( a[ j ] <= a[ i ] ) dp[ i ] = max( dp[ i ] , dp[ j ] + 1 );
		s = max( s , dp[ i ] );
	}
	printf("%d\n", s );
	
	for( int i = 1 ; i <= n ; i ++ ) {
		if( dp[ i ] == 1 ) Add_Edge( S , i , 1 );
		if( dp[ i ] == s ) Add_Edge( n + i , T , 1 );
	}
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j < i ; j ++ )
			if( a[ j ] <= a[ i ] && dp[ i ] == dp[ j ] + 1 ) Add_Edge( j + n , i , 1 );
	for( int i = 1 ; i <= n ; i ++ ) Add_Edge( i , n + i , 1 );
	printf("%d\n", Dinic( S , T ) );
	
	memset( Head , 0 , sizeof( Head ) ); Enum = 1;
	for( int i = 1 ; i <= n ; i ++ ) {
		if( dp[ i ] == 1 ) Add_Edge( S , i , i == 1 ? Inf : 1 );
		if( dp[ i ] == s ) Add_Edge( n + i , T , i == n ? Inf : 1 );
	}
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = 1 ; j < i ; j ++ )
			if( a[ j ] <= a[ i ] && dp[ i ] == dp[ j ] + 1 ) Add_Edge( j + n , i , 1 );
	for( int i = 1 ; i <= n ; i ++ ) Add_Edge( i , n + i , ( i == 1 || i == n ) ? Inf : 1 );
	printf("%d\n", Dinic( S , T ) );
    return 0;
}

进阶题

7.P2765 魔术球问题

考虑将两个能放在一起的球之间连一条边,因为要求球要依次放,所以边由编号较小的球连向编号较大的。

那么一个柱子可看作有向图上的一条简单路径。

原问题即转化为 nn 条不相交的简单路径最多能覆盖多少点。

很像第 44 题,枚举答案可以发现前几项:

1,3,7,11,17.231,3,7,11,17.23

作差得到:

2,4,4,6,62,4,4,6,6

那么可以先算出球数,然后用第四题的方法构造答案即可。

#include <queue>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
#define Inf 0x3f3f3f3f

const int MAXN = 3200 , MAXM = MAXN * ( MAXN + 2 );
struct node { int v , flw , nxt; }Graph[ 2 * MAXM + 5 ];
int Enum = 1 , Head[ MAXN + 5 ];
void Add_Edge( int u , int v , int f ) {
	Graph[ ++ Enum ] = { v , f , Head[ u ] }; Head[ u ] = Enum;
	Graph[ ++ Enum ] = { u , 0 , Head[ v ] }; Head[ v ] = Enum;
}

int n , k , S , T;
int lev[ MAXN + 5 ] , cur[ MAXN + 5 ] , nxt[ MAXN + 5 ] , sta[ MAXN + 5 ];
bool Layering( int s , int t ) {
    memset( lev , -1 , sizeof( lev ) );
	memcpy( cur , Head , sizeof( Head ) );
    queue< int > Que;
    Que.push( s ) , lev[ s ] = 0;
    while( !Que.empty( ) ) {
        int u = Que.front( ); Que.pop( );
        for( int i = Head[ u ] ; i ; i = Graph[ i ].nxt ) {
            int v = Graph[ i ].v , flw = Graph[ i ].flw;
            if( flw > 0 && lev[ v ] == -1 )
                lev[ v ] = lev[ u ] + 1 , Que.push( v );
        }
    }
    return lev[ t ] != -1;
}
int dfs( int u , int t , int f ) {
	if( u == t ) return f;
	for( int i = cur[ u ] ; i ; i = Graph[ i ].nxt ) {
		int v = Graph[ i ].v , flw = Graph[ i ].flw;
		cur[ u ] = i;
		if( flw > 0 && lev[ u ] < lev[ v ] ) {
			int mf = dfs( v , t , min( f , flw ) );
			if( mf ) {
				Graph[ i ].flw -= mf; Graph[ i ^ 1 ].flw += mf;
				if( u != S && v > n ) sta[ v - n ] = 1;
				nxt[ u ] = v;
				return mf;
			}
		}
	}
	return 0;
}
int Dinic( int s , int t ) {
	int Maxf = 0;
	while( Layering( s , t ) ) for( int fl ; ( fl = dfs( s , t , Inf ) ) > 0 ; Maxf += fl );
	for( int i = 1 ; i <= n ; i ++ )
		if( !sta[ i ] ) {
			printf("%d", i );
			int u = i;
			for( int u = i ; nxt[ u ] && nxt[ u ] != t ; u = nxt[ u ] - n ) printf(" %d", nxt[ u ] - n );
			printf("\n");
		}
	return Maxf;
}

bool sqt[ MAXN * MAXN + 5 ];
int main( ) {
	scanf("%d",&k); n = ( k * ( k + 2 ) + ( k & 1 ) - 2 ) / 2;
	printf("%d\n", n );
	
	S = 2 * n + 1 , T = S + 1;
	for( int i = 1 ; i <= n ; i ++ ) sqt[ i * i ] = 1;
	for( int i = 1 ; i <= n ; i ++ )
		for( int j = i + 1 ; j <= n ; j ++ )
			if( sqt[ i + j ] ) Add_Edge( i , n + j , 1 );
	for( int i = 1 ; i <= n ; i ++ ) Add_Edge( S , i , 1 );
	for( int i = 1 ; i <= n ; i ++ ) Add_Edge( n + i , T , 1 );
	Dinic( S , T );
	return 0; 
} 

二.费用流问题